package zw_501_600.zw_599_两个列表的最小索引总和;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {

    public static void main(String[] args) {
        String[] list1 = {"Shogun", "Tapioca Express", "Burger King", "KFC"};
        String[] list2 = {"Piatti", "The Grill at Torrey Pines", "Hungry Hunter Steakhouse", "Shogun"};
        String[] restaurant = findRestaurant(list1, list2);
        for (String s : restaurant) {
            System.out.println(s);
        }

    }

    /**
     * 哈希表
     * 使用一个哈希表记录 list1中每个餐厅对应的索引下标，然后遍历 list2，
     * 如果list2中的餐厅存在于哈希表中，那么说明该餐厅是两人共同喜爱的，计算它的索引和。
     *     如果该索引和比最小索引和小，则清空结果，将该餐厅加入结果中，该索引和作为最小索引和；
     *     如果该索引和等于最小索引和，则直接将该餐厅加入结果中。
     *
     * @param list1
     * @param list2
     * @return
     */
    public static String[] findRestaurant(String[] list1, String[] list2) {
        Map<String, Integer> index = new HashMap<>();
        for (int i = 0; i < list1.length; i++) {
            index.put(list1[i], i);
        }

        List<String> ret = new ArrayList<>();
        int indexSum = Integer.MAX_VALUE;
        for (int i = 0; i < list2.length; i++) {
            if (index.containsKey(list2[i])) {
                int j = index.get(list2[i]);
                if (i + j < indexSum) {
                    ret.clear();
                    ret.add(list2[i]);
                    indexSum = i + j;
                } else if (i + j == indexSum) {
                    ret.add(list2[i]);
                }
            }
            if (i > indexSum) break;
        }
        return ret.toArray(new String[ret.size()]);
    }

}